package 动态规划;

import java.util.ArrayList;
import java.util.List;

// 问题：从顶部到底部的最小路径和
// 状态定义：从(0,0)到(i,j)的最小路径和
// 状态转移方程：F(i,j)：Math.min(F(i-1,j),F(i-1,j-1)) + array[i][j]
//            (j == 0 || j == i) : F(i,j)
//                              j == 0: F(i-1,0) + array[i][0]
//                              j == i: F(i-1,j-1) + array[i][j]
// 状态初始化：F(0,0) = array[0][0]
// 返回结果：Math.min(F(row-1,j)...)
public class LeetCode120_三角形最小路径和 {
    public int minimumTotal(List<List<Integer>> triangle) {
        if(triangle.size() == 0 ) {
            return 0;
        }
        List<List<Integer>> minPathSum = new ArrayList<>();
        for (int i = 0; i < triangle.size(); i++) {
            minPathSum.add(new ArrayList<>());
        }
        // F[0][0]初始化
        minPathSum.get(0).add(triangle.get(0).get(0));
        for (int i = 1; i < triangle.size(); i++) {
            int curSum = 0;
            for (int j = 0; j <= i; j++) {
                if (j == 0){
                    curSum = minPathSum.get(i-1).get(0);
                }else if (j == i) {
                    curSum = minPathSum.get(i-1).get(j-1);
                }else {
                    curSum = Math.min(minPathSum.get(i-1).get(j-1),
                            minPathSum.get(i-1).get(j));
                }
                minPathSum.get(i).add(triangle.get(i).get(j) + curSum);
            }
        }
        int size = triangle.size();
        int allMin = minPathSum.get(size-1).get(0);
        for (int i = 1; i < size; i++) {
            allMin = Math.min(allMin,minPathSum.get(size-1).get(i));
        }
        return allMin;
    }
}
